import java.util.ArrayList;
import java.util.List;

class Solution {

    //优美的排列
    public int ret;
    public List<Integer> path;
    public boolean[] check;
    public int[] nums;
    public int countArrangement(int n) {
        ret = 0;
        path = new ArrayList<>();
        check = new boolean[n + 1];
        nums = new int[n + 1];
        for(int i = 1; i <= n; i++){
            nums[i] = i;
        }
        dfs(1, n);
        return ret;
    }
    public void dfs(int index, int n){
        //递归出口
        if(index > n){
            ret++;
            return;
        }
        //函数体
        for(int i = 1; i <= n; i++){
            if(check[i] == false && (nums[i] % index == 0 || index % nums[i] == 0)){
                path.add(i);
                check[i] = true;

                dfs(index + 1, n);//递归

                path.remove(path.size() - 1);//回溯
                check[i] = false;
            }
        }
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        solution.countArrangement(3);
    }

}